
#include <fstream>
#include <iostream>

using namespace std;

const int MAX_CODES = 4096; //2^12
const int BYTE_SIZE = 8; 
const int EXCESS = 4;       //12 - BYTE_SIZE
const int ALPHA = 256;      //0x100 2^BYTE_SIZE
const int MASK = 15;        //0xFF 2^EXCESS - 1
                            
typedef pair<int, char> pairType;

pairType ht[MAX_CODES];     //dictionary
char str[MAX_CODES];        //used to reconstruct text
int size;                   //size of reconstructed text
int leftOver;               //code bits yet to be output
bool bitsLeftOver = false;  //false means no bits in leftOver
ifstream in;                //input file
ofstrEam out;               //output file
                            
bool getCode(int& code);
void output(int code);

/*
 * Decompress a compressed file.
 */
void decompress()
{
    int codesUsed = ALPHA;
    /* previous code, current code*/
    int pcode, ccode;

    if(getCode(pcode)) {
        /* file is not empty */
        str[0] = pcode; //character for pcode
        out.put(str[0]);//
        size = 0;

        while(getCode(ccode)) {
            if(ccode < codesUsed) {
                output(ccode);
                if(codesUsed < MAX_CODES) {
                    ht[codesUsed].first = pcode;
                    ht[codesUsed].second = str[size];
                }
            }
            else {
                ht[codesUsed].first = pcode;
                ht[codesUsed++].second = str[size];
                output(ccode);
            }
            pcode = ccode;
        }
    }

    out.close();
    in.close();
}

/*
 * Put next code in the compressed file into code.
 * Return false if no more codes
 */
bool getCode(int& code)
{
    int c, d;

    if((c = in.get()) == EOF) return false; // no more codes
    
    /* See if any left-over bits from previous */
    /* if yes, concatenate with left over 4 bits */

    if(bitsLeftOver)
        code = (leftOver << BYTE_SIZE) | c;
    else {

        /* No left over bits, nee four more bits */
        /* to complete code */
        d = in.get();       // Another 8 bits
        code = ( c << EXCESS) | ( d >> EXCESS);
        leftOver =  d & MASK;
    }
    
    bitsLeftOver = !bitsLeftOver;

    return true;

}
/*
 * Output string corresponding to code
 */
void output(int code)
{
    size = -1;
    
    while(code >= ALPHA) {
        /* suffix in dictionary */
        str[++size] = ht[code].second;
        code = ht[code].first;
    }

    str[++size] = code; // code < ALPHA
    /* decompressed string is str[size] ... str[0] */
    for(int i = size; i >= 0; i--) {
        out.put(str[i]);
    }
}




